/**
 * 斐波那契数列
  - f(0) = 0
  - f(1) = 1
  - f(n) = f(n -1) + f(n -2)
 * 递归 - O(2^n)：不可用
 */ 
// function fibonacci (n: number): number {
//   if (n <= 0) return 0
//   if (n === 1) return 1
//   return fibonacci(n - 1) + fibonacci(n - 2)
// }

// 循环 - 时间复杂度：O(n)
function fibonacci (n: number): number {
  if (n <= 0) return 0
  if (n === 1) return 1

  let n1 = 1 // 记录 n-1 的结果
  let n2 = 0 // 记录 n-2 的结果
  let res = 0
  for (let i = 2; i <= n; i++) {
    res = n1 + n2
    // 记录中间结果
    n2 = n1
    n1 = res
  }
  return res
}